package 分治;

/**
 * 427. 建立四叉树
 *给你一个 n * n 矩阵 grid ，矩阵由若干 0 和 1 组成。请你用四叉树表示该矩阵 grid 。
 * 解题思路：
 *  1：前缀和数组预处理：计算二维前缀和数组preSum，用于快速计算任意子矩阵的和；
 *  2：递归构建四叉树：
 *      对于当前子矩阵，使用前缀和数组判断其是否全为0或者全为1；
 *      如果是，则创建一个叶子节点；
 *      否则，将当前子矩阵分为四个子区域，递归构建每个子区域的四叉树节点，并创建非叶子节点；
 */
public class L_427 {

    public Node construct(int[][] grid) {
        int n = grid.length;
        int[][] preSum = new int[n + 1][n + 1];
        // 构建前缀和
        for (int i = 1; i <= n ; i++) {
            for (int j = 1; j <= n ; j++) {
                preSum[i][j] = grid[i-1][j-1] + preSum[i-1][j]+preSum[i][j-1] - preSum[i-1][j-1];
            }
        }
        return constructHelper(0,0,n,preSum);
    }

    private Node constructHelper(int r, int c, int len, int[][] preSum){
        // 获取子矩阵的和
        int sum = getSum(r,c,len,preSum);
        // 如果子矩阵的和为0或者全为1，则创建叶子节点
        if (sum == 0){
            return new Node(false,true);
        }else if (sum == len*len){
            return new Node(true,true);
        }else { // 如果子矩阵的和不为0且不全为1，则创建非叶子节点
            int half = len/2;
            // 上下左右四个方向递归回溯
            Node topLeft = constructHelper(r,c,half,preSum);
            Node topRight = constructHelper(r,c+half,half,preSum);
            Node bottomLeft = constructHelper(r+half,c,half,preSum);
            Node bottomRight = constructHelper(r+half,c+half,half,preSum);
            return new Node(false,false,topLeft,topRight,bottomLeft,bottomRight);
        }
    }


    /**
     * 计算子矩阵的和
     * @param r
     * @param c
     * @param len
     * @param preSum
     * @return
     */
    private int getSum(int r,int c,int len,int[][] preSum){
        int r1 = r + len;
        int c1 = c + len;
        return preSum[r1][c1] - preSum[r][c1] - preSum[r1][c] + preSum[r][c];
    }

    class Node {
        public boolean val; // 值
        public boolean isLeaf; // 是否为叶子节点
        public Node topLeft; // 上左子节点
        public Node topRight; // 上右子节点
        public Node bottomLeft; // 下左子节点
        public Node bottomRight; // 下右子节点


        public Node() {
            this.val = false;
            this.isLeaf = false;
            this.topLeft = null;
            this.topRight = null;
            this.bottomLeft = null;
            this.bottomRight = null;
        }

        public Node(boolean val, boolean isLeaf) {
            this.val = val;
            this.isLeaf = isLeaf;
            this.topLeft = null;
            this.topRight = null;
            this.bottomLeft = null;
            this.bottomRight = null;
        }

        public Node(boolean val, boolean isLeaf, Node topLeft, Node topRight, Node bottomLeft, Node bottomRight) {
            this.val = val;
            this.isLeaf = isLeaf;
            this.topLeft = topLeft;
            this.topRight = topRight;
            this.bottomLeft = bottomLeft;
            this.bottomRight = bottomRight;
        }
    }
}
